UVa/10373 - The brick stops here/10373.cpp

   1 //10373 - The brick stops here
   2 #include <iostream>
   3 using namespace std;
   4
   5 const int MAXM = 20, MAXN = 200, MAXSUM = MAXM * 1000;
   6
   7 unsigned int dp[MAXM+1][MAXSUM+1];
   8 int w[MAXN], p[MAXN];
   9
  10 void check(bool b){
  11   while (!b);
  12 }
  13
  14 int main(){
  15   int runs;
  16   scanf("%d", &runs);
  17   for (int run=0; run<runs; ++run){
  18     if (run) printf("\n");
  19
  20     int n, sum = 0;
  21     scanf("%d", &n);
  22     for (int i=0; i<n; ++i){
  23       scanf("%d %d", &w[i], &p[i]);
  24       check(1 <= w[i] && w[i] <= 999);
  25       sum += w[i];
  26     }
  27
  28     sum = std::min(sum, MAXSUM);
  29     for (int i=0; i<=MAXM; ++i)
  30       for (int j=0; j<=sum; ++j)
  31         dp[i][j] = INT_MAX;
  32
  33     dp[0][0] = 0;
  34     dp[1][w[0]] = p[0];
  35     for (int k=1; k<n; ++k){
  36       //en este momento, dp[i][j] = minimo precio en que puedo escoger i ladrillos entre los ladrillos [0..k]
  37       //tal que la suma neta de cobre sea j.
  38       for (int i=MAXM; i>=1; --i){ //i va descendiendo para no ir a usar el mismo ladrillo dos veces.
  39         for (int j=0; j <=sum; ++j){
  40           if (j - w[k] >= 0){
  41             dp[i][j] = std::min(dp[i][j], dp[i-1][j-w[k]] + p[k]);
  42           }
  43         }
  44       }
  45     }
  46
  47     int c;
  48     scanf("%d", &c);
  49     while (c--){
  50       int m, cmin, cmax;
  51       scanf("%d %d %d", &m, &cmin, &cmax);
  52       check(0 <= m && m <= 20);
  53       check(1 <= cmin && cmin <= 999);
  54       check(1 <= cmax && cmax <= 999);
  55
  56       unsigned int answer = INT_MAX;
  57       for (int j=m*cmin; j<=m*cmax && j <=sum; ++j){
  58         //if (answer > dp[m][j]) printf("better answer: dp[%d][%d] = %u\n", m, j, dp[m][j]);
  59         answer = std::min(answer, dp[m][j]);
  60       }
  61       if (answer < INT_MAX){
  62         printf("%u\n", answer);
  63       }else{
  64         printf("impossible\n");
  65       }
  66     }
  67   }
  68   return 0;
  69 }